1. Field of the Invention
The present invention relates to an apparatus for and a method of generating a straight line in a discrete coordinate system, and more specifically to generation of a straight line of pixels by utilizing, for example, the Bresenham algorithm.
2. Prior Art
As a method of generating a straight line of pixels, such a method as DDA (Digital Differential Analysis) system has been known. Japanese Patent Public Disclosure No. 94378/85 discloses an example wherein the DDA system has been realized. FIG. 1 is a block diagram illustrating the construction of a straight line generator which employs the conventional DDA system. The reference numeral 51 designates an X-counter which increases or decreases an X coordinate; 52 a Y-counter which increases or decreases a Y coordinate; 53 a slope register adapted to hold the gradient of a slope; 54 an adder adapted to accumulate the content of the slope register; 55 a register adapted to hold the content of the adder 54; and 56, 57 selectors adapted to select carry signal from the adder 54 and a clock signal. The slope register 53, the adder 54 and the register 55 constitute a decimal-fraction calculating circuit adapted to compute a decimal fraction.
The operation of the DDA system will now be explained by referring to FIG. 1. Using the coordinate (XS, YS) of the start point and the coordinate (XE, YE) of the end point of a straight line the absolute value .vertline.X.vertline.=.vertline.XE-XS.vertline. of a difference value X of the X coordinate components and the absolute value .vertline.Y.vertline.=.vertline.YE-YS.vertline. of a difference value Y of the Y coordinate components between those two points are calculated by a circuit provided outside the straight line generator. (It is to be understood that the coordinate axis which corresponds to a large one of the absolute values .vertline.X.vertline. and .vertline.Y.vertline. will be referred to as the main axis.) It is assumed here that the X axis is the main axis. The slope of the line can be obtained by calculating the ratio between such two absolute values. In this case, it is also assumed that a larger absolute value of the respective coordinate components is used as a denominator and a smaller absolute value of the respective coordinate components is used as a numerator so as to calculate the ratio. Since the denominator is larger than the numerator, the ratio obtained is a decimal fraction less than unity. In this way, the ratio is equal to .vertline.Y.vertline./.vertline.X.vertline.. First, after the register 55 has been reset, the ratio is loaded in the slope register 53, the X coordinate of the start point in the X-counter 51 and the Y coordinate of the start point in the Y-counter 52, respectively. The selectors 56, 57 operate to supply the clock signal to the counter for the main coordinate axis and the carry signal generated by the adder 54 at the time of adding the ratio output from the slope register 53 for every clock, to the counter for the rest of the coordinate axes. This causes the counter corresponding to the main coordinate axis to be operated for each clock and the counter for the rest of the coordinate axes to be operated by the carry signal output from the adder 54, whereby the X-counter 51 and the Y-counter 52 calculate interpolated coordinate values from the start point to the end point of the line and output such values. By repeating this operation, pixels making a straight line may be generated.
Besides the method explained above, many other methods of line drawing have been employed. Among them, a method of which the algorithm is simple and which is suitable for implementation in hardware is the Bresenham method which is very widely utilized today. A hardware version of a line drawing process using the Bresenham algorithm is found in Japanese Patent Public Disclosure No. 165280/87 filed by IBM Corp. with the title of "Set-up Apparatus for Graphic Vector Generator".
In the Bresenham algorithm, although it is not described in detail here, either one of the coordinate values is varied by .+-.1. The other of the coordinates may be varied or not depending on the value of an error term. The error term means a recorded distance between a correct path on a line measured to the direction perpendicular to the maximum variation axis (the main axis) and a point actually generated. In the case of .vertline.X.vertline..gtoreq..vertline.Y.vertline., since the X axis is the maximum variation axis (or the main axis), the error term e is accordingly measured in the Y axis direction. It is to be noted here that the error term e is utilized to make a decision of being positive or negative and may be added by an integer for use.
Since a straight line generator according to the prior art is constituted as shown in FIG. 1, division has to be performed to compute the slope of the line and generation of parameters for such division takes time, resulting in a reduction in processing performance. In addition, the rate of time generation is also reduced due to the fact that data used for calculation are decimal fractions and therefore long.
Furthermore, since the "Set-up Apparatus for Graphic Vector Generator" disclosed in the above Japanese Patent Public Disclosure Official Gazette is an apparatus in which the symmetry of graphics is taken into consideration, parameters relating to X coordinate values have, in some conditions, to be exchanged with parameters relating to Y coordinate values. This necessitates a "swapping circuit", resulting in a large hardware scale and a long parameter setting-up time.